package org.example.method;

import org.example.graph.Edge;
import org.example.graph.Vertex;

import java.util.ArrayList;
import java.util.List;

public class Prim {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        Vertex v7 = new Vertex("v7");

        v1.edges = List.of(new Edge(v2,2),
                new Edge(v4,1),
                new Edge(v3,4));

        v2.edges = List.of(new Edge(v1,2),
                new Edge(v4,3),
                new Edge(v5,10));
        v3.edges = List.of(new Edge(v1,4),
                new Edge(v6,5),
                new Edge(v4,2));
        v4.edges = List.of(new Edge(v1,1),
                new Edge(v2,3),
                new Edge(v3,2),
                new Edge(v5,7),
                new Edge(v6,8),
                new Edge(v7,4));
        v5.edges = List.of(new Edge(v2,10),
                new Edge(v7,6),
                new Edge(v4,7));
        v6.edges = List.of(new Edge(v3,5),
                new Edge(v7,1),
                new Edge(v4,8));
        v7.edges = List.of(new Edge(v5,6),
                new Edge(v6,1),
                new Edge(v4,4));

        List<Vertex> graph = new ArrayList<>(List.of(v1, v2, v3, v4, v5,v6,v7));


        prim(graph, v1);
    }

    private static void prim(List<Vertex> graph, Vertex source) {
        ArrayList<Vertex> list = new ArrayList<>(graph);
        source.dist = 0;

        while (!list.isEmpty()){
            //2.找到最短路径的点
            Vertex cur = chooseMinDistVertex(list);
            //3.跟新附近的所有节点
            updateDist(cur);
            //4.删除现在的节点
            list.remove(cur);
            cur.visited = true;
        }

        for (Vertex vertex : graph) {
            System.out.println(vertex.getName() +" 长度："+ vertex.dist + "   路径" + vertex.path.toString());

        }
    }

    private static void updateDist(Vertex cur) {
        for (Edge edge : cur.edges) {
            int dist = edge.weight;
            Vertex vertex = edge.linked;
            if (!vertex.visited){
                if (dist < vertex.dist){
                    vertex.dist = dist;
                    //更新路径
                    vertex.path = new ArrayList<>(cur.path);
                    vertex.path.add(cur.getName());
                }
            }
        }
    }

    /**
     * 选择并更新最小点
     * @param list
     * @return
     */
    private static Vertex chooseMinDistVertex(ArrayList<Vertex> list) {
        Vertex vertex = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            Vertex current = list.get(i);
            if (current.dist < vertex.dist){
                vertex = current;
            }
        }

        return vertex;
    }
}
